<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Code Factoring Optimizations</title>
<link rel="stylesheet" type="text/css" href="https://gcc.gnu.org/gcc.css" />
</head>

<body>
<h1>Code Factoring Optimizations</h1>

<h2>Table of Contents</h2>

<ul>
<li><a href="#news">Latest news (last updated: 2005-08-11)</a></li>
<li><a href="#intro">Introduction</a></li>
<li><a href="#contributing">Contributing</a></li>
<li><a href="#documentation">Documentation</a></li>
<li><a href="#features">Features</a></li>
<li><a href="#preresults">Preliminary results</a></li>
<li><a href="#todo">To do</a></li>
</ul>

<h2 id="news">Latest News</h2>

<dl>
<dt>2005-08-11</dt>
<dd><p>Add sequence abstraction on tree, add sinking part of local factoring on Tree-SSA.</p></dd>
<dt>2005-02-02</dt>
<dd><p>Some more details about the algorithms and some preliminary results 
added. To do list published.
</p></dd>
<dt>2004-11-16</dt>
<dd><p>The branch is now open.
</p></dd>
</dl>

<h2 id="intro">Introduction</h2>

<p>Code factoring is the name of a class of useful optimization techniques 
developed especially for code size reduction. These approaches aim to reduce
size by restructuring the code.</p>

<p>The goal of this project is to add a new extension for improving the code
size optimization of GCC with code factoring methods (code motion and merging
algorithms). The implementation currently resides on the branch.</p>

<h2 id="contributing">Contributing</h2>

<p>Checkout the cfo-branch branch from our respository.</p>

<p>When posting to the development lists, please mark messages and patches with
[cfo] in the subject. The usual contribution and testing rules apply. This
branch is maintained by <a href="mailto:loki@gcc.gnu.org">Gabor Loki</a>.</p>

<h2 id="documentation">Documentation</h2>

<p>The project includes the following two code factoring algorithms:</p>
<ul>
<li>Local code factoring: This is a code motion technique. It moves identical 
instructions from basic blocks to their common predecessor or successor, if 
they have any. The semantics of the program have to be preserved of course, 
therefore only those instructions may be moved, which neither invalidate any
existing dependencies nor introduce new ones. To obtain the best size 
reduction some of the instructions are moved upward (code hoisting) to the 
common predecessor, while some are moved downward (code sinking) to the 
common successor.<br />
C code example:<br />
<pre>
// Original source            // After local factoring
{                             {
                                I1;   // &lt;= HOIST
  if ( cond )                   if ( cond )
  {                             {
    I0;                           I0;
    I1;   // &lt;= HOIST
    I2;   // &lt;= SINK
    I3;   // &lt;= SINK
  }                             }
  else                          else
  {                             {
    I1;   // &lt;= HOIST
    I4;                           I4;
    I5;                           I5;
    I2;   // &lt;= SINK
    I3;   // &lt;= SINK
  }                             }
                                I2;   // &lt;= SINK
                                I3;   // &lt;= SINK
}                             }
</pre>
</li>
<li>Sequence abstraction: It is a size optimization method. Unlike local 
factoring, this works with whole basic blocks instead of single instructions. 
The main idea of this technique is to find identical sequences of code, which 
can be turned into procedures and then replace all occurrences with calls to
the newly created subrutine. It is kind of an opposite of function inlining.<br />
C code example:<br />
<pre>
// Original source            // After sequence abstraction
{                             {
                                void *jump_label;
  ...                           ...
                                jump_label = &amp;&amp;exit_0;
                              entry_0:
  I0;                           I0;
  I1;                           I1;
  I2;                           I2;
  I3;                           I3;
                                goto *jump_label;
                              exit_0:
  ...                           ...
                                jump_label = &amp;&amp;exit_1;
                              goto entry_0;
  I0;
  I1;
  I2;
  I3;
                              exit_1:
  ...                           ...
                                jump_label = &amp;&amp;exit_2;
                                goto entry_0;
  I0;
  I1;
  I2;
  I3;
                              exit_2:
  ...                           ...
                                jump_label = &amp;&amp;exit_3;
                                goto entry_0;
  I0;
  I1;
  I2;
  I3;
                             exit_3:
  ...                           ...
}                             }
</pre>
</li>
</ul>

<p>Both algorithms have an opportunity of working on two different levels 
(Tree and RTL). Both have their own advantages and disadvantages.
This project holds both types for future investigations. </p>

<p>For more information about code factoring see the article in the
<a href="https://gcc.gnu.org/pub/gcc/summit/2004/Code%20Factoring.pdf">
GCC Summit Proceedings (2004)</a>.</p>

<h2 id="features">Features</h2>

<p>Currently the following algorithms are implemented on the branch:</p>

<ul>
<li>Local factoring on RTL (<code>-frtl-lfact</code>)</li>
<li>Local factoring on Tree-SSA (<code>-ftree-lfact</code>)</li>
<li>Sequence abstraction on RTL (<code>-frtl-seqabstr</code>)</li>
<li>Sequence abstraction on Tree (<code>-ftree-seqabstr</code>)</li>
</ul>

<h2 id="preresults">Preliminary results</h2>

<p>The following results have been prepared using the 
<a href="http://szeged.github.io/csibe/">CSiBE</a> benchmark with respect
to the mainline at the last merge (2005-07-11).</p>

<table class="right">
<tr>
  <th></th>
  <th class="center" colspan="2">Code size save</th>
  <th class="center" colspan="2">Compilation time multiplier</th>
</tr>
<tr>
  <td>Target</td>
  <td class="center">arm-elf</td>
  <td class="center">i686-linux</td>
  <td class="center">arm-elf</td>
  <td class="center">i686-linux</td>
</tr>
<tr>
  <td>Sequence abstraction on RTL</td>
  <td>1.07%</td>
  <td>1.43%</td>

  <td>1.94</td>
  <td>1.26</td>
</tr>
<tr>
  <td>Sequence abstraction on Tree</td>
  <td>0.34%</td>
  <td>0.18%</td>

  <td>1.25</td>
  <td>1.25</td>
</tr>
<tr>
  <td>Local factoring on RTL</td>
  <td>0.11%</td>
  <td>0.19%</td>

  <td>1.01</td>
  <td>0.99</td>
</tr>
<tr>
  <td>Local factoring on Tree-SSA</td>
  <td>0.31%</td>
  <td>0.24%</td>

  <td>1.02</td>
  <td>1.01</td>
</tr>
<tr>
  <td><b>Overall</b></td>
  <td><b>1.96%</b></td>
  <td><b>1.94%</b></td>

  <td><b>2.08</b></td>
  <td><b>1.49</b></td>
</tr>
</table>

<h2 id="todo">To do</h2>

<ul>
<li>Implement procedural abstraction on IPA (interprocedural version of
sequence abstraction).</li>
<li>Improve the compilation time of the sequence abstraction using
fingerprinting.</li>
<li>Improve algorithms with merging similar instead of identical 
instructions/sequences.</li>
</ul>

</body>
</html>
